package arrAndstr;

import MetaApp.One;

import java.util.*;

/*
    146. LRU 缓存
    优化思路：
        使用 LinkedHashMap 优化
        LinkedHashMap：
            既能保证 set 的唯一性
            也能保证顺序
 */
public class T146 {
    public static void main(String[] args) {
        LRUCache lruCache = new LRUCache(2);
        System.out.println(lruCache.get(2));
        lruCache.put(2,6);
        System.out.println(lruCache.get(1));
        lruCache.put(1,5);
        lruCache.put(1,2);
        System.out.println(lruCache.get(1));
        System.out.println(lruCache.get(2));

    }

    static class LRUCache {
        private Map<Integer, Integer> map;
        private int capacity;
        private List<Integer> list; // 用list替代queue

        public LRUCache(int capacity) {
            this.map = new HashMap<>();
            this.capacity = capacity;
            this.list = new ArrayList<>();
        }

        public int get(int key) {
            if (!this.map.containsKey(key)) {
                return -1;
            }
            // 如果存在，需要把它再放到最后面
            this.list.remove((Integer) key);
            this.list.add(key);
            return this.map.get(key);
        }

        public void put(int key, int value) {
            if (this.map.size()==capacity && !this.map.containsKey(key)) {
                Integer removeKey = this.list.get(0);
                this.list.remove(0);
                this.map.remove(removeKey);
            }
            if (this.map.containsKey(key)) {
                this.list.remove((Integer) key);
            }
            this.list.add(key);
            this.map.put(key, value);
        }
    }
}
